Triangle intersection
We wish to find out when a ray hits a triangle. This is done by first checking if the ray hits the plane that the triangle lies in. If the ray hits the plane, a second test checks if the hit point is contained within the triangle bounds.
Our triangle will be defined by three vertices, \( \mathbf{a} \), \( \mathbf{b} \), \( \mathbf{c} \). The order of the vertices is used to define the 'front' and 'back' of the triangle. OpenGL and many graphics applications define the front of the triangle as the side where the vertices wind counter-clockwise. With this winding, the normal \( \mathbf{n} \) can be computed as:
$$ \mathbf{n} = (\mathbf{b} - \mathbf{a}) \times (\mathbf{c} - \mathbf{b}) $$
The plane that the triangle lies in can be defined using the implicit plane equation which requires a point on the plane and the plane normal:
$$ (\mathbf{p} - \mathbf{a}) \cdot \mathbf{n} = 0 $$
where \( \mathbf{p} \) is the a possible position on the surface, \( \mathbf{a} \) is a point on the plane (in this case, the triangle vertex \( \mathbf{a} \), and \( \mathbf{n} \) is the plane normal.
Given the parametric equation of a ray $$ \mathbf{r} = \mathbf{e} + t\mathbf{d}\ $$ we can solve for the intersection by setting the equations equal to one another. Put the ray equation in place of the \( \mathbf{p}\) in the surface equation results in:
$$ (\mathbf{e} + t\mathbf{d} - \mathbf{a}) \cdot \mathbf{n} = 0; $$
We can then solve for t: $$ t = \frac{ (\mathbf{a} - \mathbf{e}) \cdot \mathbf{n}} {\mathbf{d} \cdot \mathbf{n}} $$
Using \(t\) the location \( \mathbf{x} \) where the ray intersects the plane can be computed (using the ray equation).
The intersection point must then be tested to find if the point is within the triangle boundaries. This can be done walking around the triangle's vertices and verifying that the intersection point is always on the left. If so, the times product can be used to produce a vector that is parallel to the surface normal. Three tests must be performed:
$$ (\mathbf{b} - \mathbf{a}) \times (\mathbf{x} - \mathbf{a}) \cdot \mathbf{n} > 0 $$ $$ (\mathbf{c} - \mathbf{b}) \times (\mathbf{x} - \mathbf{b}) \cdot \mathbf{n} > 0 $$ $$ (\mathbf{a} - \mathbf{c}) \times (\mathbf{x} - \mathbf{c}) \cdot \mathbf{n} > 0 $$
If all three conditions above pass, then the intersection point lies within the triangle bounds and the hit is valid.
There are several other triangle intersection algorithms. A more complex algorithm is based on barycentric coordinates, but it allows easier texture coordinate calculations.